package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_18_四数之和 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{1,0,-1,0,-2,2},0).toString());
//        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{2,2,2,2,2},8).toString());
//        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{-5,0,1,1,4},0).toString());
//        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{-2,-1,-1,1,1,2,2},0).toString());
//        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{0,0,0,1000000000,1000000000,1000000000,1000000000},1000000000).toString());
        System.out.println(new 力扣_18_四数之和().fourSum(new int[]{0,0,0,-1000000000,-1000000000,-1000000000,-1000000000},-1000000000).toString());
    }

    /**
    题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
     请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 
     （若两个四元组元素一一对应，则认为两个四元组重复）：
     0 <= a, b, c, d < n
     a、b、c 和 d 互不相同
     nums[a] + nums[b] + nums[c] + nums[d] == target
     你可以按 任意顺序 返回答案 。

     示例 1：
     输入：nums = [1,0,-1,0,-2,2], target = 0
     输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

     示例 2：
     输入：nums = [2,2,2,2,2], target = 8
     输出：[[2,2,2,2]]

    分析：
       1.排序、双指针、O(n*n*logn)
        优化: 及早判跳出 不比较的循环
            1.去重没有做好 -- 一二层循环时，如果与上一次的数字相等，大可排除，因为已经包含过一次结果了
            2.循环的前4个和 > target  跳出

    边界值 & 注意点：
       1.不能有重复答案
       2.不能用相加，因为会溢出 ，相减也会  最好转long
       3.判断重复有点麻烦，直接set
     **/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int length = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < length-3; i++) {
            if((i > 0 &&nums[i] ==nums[i-1]))continue;
            if((long)target-nums[i]-nums[i+1]-nums[i+2]-nums[i+3]<0 )break;
            if((long)target-nums[length-3]-nums[length-2]-nums[length-1]-nums[i]>0 )continue;

            for (int j = i+1; j < length-2; j++) {
                if(j > i+1 &&nums[j] ==nums[j-1])continue;
                if((long)target-nums[i]-nums[j]-nums[j+1]-nums[j+2]<0 )break;
                if((long)target-nums[length-3]-nums[length-2]-nums[length-1]-nums[i]>0 )continue;

                int left =j+1,right=length-1,sum =target-(nums[i]+nums[j]);
                while (left<right){
                    if(sum > nums[left]+nums[right]){
                        left++;
                    }else if(sum < nums[left]+nums[right]){
                        right--;
                    }else{
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1])
                            left++;
                        left++;
                        while (left < right && nums[right] == nums[right - 1])
                            right--;
                        right--;
                    }
                }
            }
        }
        return  res;
    }
}
